package com.hsc.offer;

/**
 * @author
 * @date 2025-07-04
 * @Description 22、输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。
 * 如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。
 */
public class OfferTest17 {
    public static void main(String[] args) {
        // 满足 二叉搜索树  后序遍历的数组
        int[] arr = {1, 4, 7, 6, 3, 13, 14, 10, 8};
        System.out.println("VerifySquenceOfBST(arr) = " + VerifySquenceOfBST(arr));
    }


    public static boolean VerifySquenceOfBST(int[] sequence) {
        // 数组为空时，题目要求返回false（因为题目要求是序列，而序列为空则无法构成二叉树，所以返回false）
        if (sequence.length <= 0) {
            return false;
        }

        // 创建一个的方法进行判断 isBST  判断数组中的所有的元素是否满足要求
        return isBST(sequence, 0, sequence.length);

    }

    /**
     * 具体判断的方法
     * 左闭右开区间
     * //什么是二叉树的后序遍历？
     * //什么是二叉搜索树? 二叉搜索树中，任何一个节点，左边的节点都比自己小，右边的节点都比自己大
     * <p>
     * //后序遍历特点：
     * // 特点1：根节点在最后。
     * // 特点2：当前二叉树的后序遍历的子树的部分，也是后序遍历。
     * //二叉搜索树的根节点的特点：
     * // 特点3：根节点左边的，都比自己小，根节点右边的都比自己大。
     * <p>
     * //二叉搜索树的后序遍历的特点：最后一个节点为根节点，我们可以从第一个节点开始找。
     * //找到第一个比根节点大的节点，这个节点左边的部分，为左子树，右边的部分为右子树。
     * //也就是说，如果说这棵树是二叉搜索树后序遍历，那么找到第一个比根节点大的节点之后。
     * //后面的每个节点，都得比根节点大，如果右任何一个节点比根节点小了，那么这个遍历结果，就不是二叉搜索树的后序遍历。
     *
     * @param sequence
     * @param start    数组开始位置
     * @param end      数组结束位置
     * @return
     */
    private static boolean isBST(int[] sequence, int start, int end) {
        // 递归的终止条件是当区间长度小于等于0时，返回true（因为空树也满足条件）。
        if (start >= end) {
            return true;
        }
        int root = sequence[end - 1];      // 当前根节点值
        int pos = 0;
        // 根据提供的后序遍历的数组sequence得出  最后一个元素为根节点
        // 从左向右遍历当前区间（从start到end-2），找到第一个大于根节点的元素，记录位置pos。
        for (pos = start; pos < end - 1; pos++) {
            //  1. 后序遍历的最后一个元素是根节点。
            if (sequence[pos] > root) { // 满足特点三：左边的元素都比根节点小 特点一：根节点元素在最后
                // 得到pos的位置的值
                break; //break之后，pos的值，第一个比根节点大的节点的位置。
            }
        }
        // 3. 检查右子树部分是否都大于根节点，如果出现小于根节点的元素，则返回false。
        // 从pos位置开始继续遍历到end-2，检查是否所有元素都大于根节点。如果遇到一个小于等于根节点的元素，则返回false。
        for (int i = pos; i < end - 1; i++) {
            // 如果其中有一个不满足 直接返回false
            if (sequence[i] < root) {
                return false;
            }
        }
        //  4. 递归检查左子树和右子树是否满足同样的条件。
        // 划分左右子树 再次分别进行递归判断
        // isBST(sequence,start,pos) 根节点左子树每个节点 也要满足二叉搜索树的特点
        // isBST(sequence,pos,end-1) 根节点的右子树每个节点 也要满足二叉搜索树的特点
        // 为什么递归调用右子树时是[pos, end-1)？因为右子树部分不包括根节点，而根节点是end-1，所以右子树区间是从pos开始到end-1（不包括end-1，因为end-1是根节点，已经排除）。
        return isBST(sequence, start, pos) && isBST(sequence, pos, end - 1);
    }

}
